/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/previous-permutation
   @Language: C++
   @Datetime: 16-02-09 08:22
   */

class Solution {
public:
	/**
	 * @param nums: An array of integers
	 * @return: An array of integers that's previous permuation
	 */
	/** Tips : this is same as next permutation
	 * see problem 52 for full steps
	 * */
	vector<int> previousPermuation(vector<int> &nums) {
		// Method 1 : STL Algorithm
		// prev_permutation(nums.begin(),nums.end());
		// return nums;
		// Method 2 : do it by yourself
		if (nums.size()<2) return nums;
		vector<int>::iterator i, j, k;
		for (i=nums.end()-1; i!=nums.begin();){
			j = i--;    // find last decreasing pair (i,i+1)
			if (!(*i > *j)) continue;
			// find last k which less than i,
			for (k=nums.end(); !(*i > *(--k)););
			iter_swap(i,k);
			// now the range [j,end) is in ascending order
			reverse(j,nums.end());
			return nums;
		}
		// current nums is in ascending order
		reverse(nums.begin(),nums.end());
		return nums;
	}
};
